/**
 * Created with IntelliJ IDEA.
 * Description:
 * https://gitee.com/li--jiaqiang/java-test.git
 * git pull
 * git pull origin master
 * git pull origin master --allow-unrelated-histories
 * User: 86187
 * Date: 2022-05-08
 * Time: 17:48
 */

//Scanner scan = new Scanner(System.in);


class Node {
    int val;
    Node next = null;

    Node(int val) {
        this.val = val;
    }
}


public class ListNode2 {

    public Node head = null;

    //尾插法
    public void addLast(int data) {
        Node newNode = new Node(data);

        if(this.head == null) {
            this.head = newNode;
        } else {
            Node pos = this.head;
            while(pos.next != null) {
                pos = pos.next;
            }
            pos.next = newNode;
        }
    }

    /**
     *给你链表的头节点 head ，每k个节点一组进行翻转，请你返回修改后的链表。
     * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public Node reverseKGroup(Node head, int k) {
        if(k <= 1) {
            return head;
        }
        Node cur = head;
        Node prev = head;
        Node tail = head;
        while(tail != null ) {
            int m = k;
            while(m != 0) {
                if(tail == null && m >= 1) {
                    return head;
                }
                prev = tail;
                tail = tail.next;
                m--;
            }
            if(cur == head) {
                Node tmp = cur.next;
                while(tmp != tail) {
                    Node newNext = tmp.next;
                    tmp.next = head;
                    head = tmp;
                    tmp = newNext;
                }
                cur.next = tail;
            } else {
                Node newHead = prev;
                prev = cur;
                cur = cur.next;
                Node newTail = cur;
                Node tmp = cur.next;
                while(tmp != tail) {
                    Node newNext = tmp.next;
                    tmp.next = cur;
                    cur = tmp;
                    tmp = newNext;
                }
                prev.next = newHead;
                newTail.next = tail;
                cur = newTail;
            }
        }
        return head;
    }

    //打印方法
    public void display(Node head) {
        Node pos = head;
        while(pos != null) {
            System.out.print(pos.val+" ");
            pos = pos.next;
        }
        System.out.println();
    }
}
